package com.masterlu.leetcode.daily.greedy.simple;

import java.util.ArrayList;
import java.util.List;

/**
 * 944. 删列造序
 * https://leetcode-cn.com/problems/delete-columns-to-make-sorted/
 *
 * @date created in 2021/6/7 10:06
 */
public class S944MinDeletionSize {

    public int minDeletionSize(String[] strs) {

        List<Integer> list = new ArrayList<>();
        int delCount = 0;
        for (int i = 0; i < strs.length - 1; i++) {
            //按列，逐列进行比对，判断是否有序
            for (int j = 0; j < strs[0].length(); j++) {
                //判断当前列是否
                if (list.contains(j)) {
                    continue;
                }
                if (strs[i].charAt(j) - strs[i + 1].charAt(j) > 0) {
                    delCount++;
                    //记录不匹配的列
                    list.add(j);
                }
            }
        }

        return delCount;
    }
}
